import java.util.*;


public class Solution11 {
    public static void main(String[] args) {
        Solution11 solution = new Solution11();
        TreeNode t1= new TreeNode(1);
        TreeNode t2= new TreeNode(3);
        TreeNode t3= new TreeNode(2);
        TreeNode t4= new TreeNode(5);
        TreeNode t5= new TreeNode(3);
        TreeNode t6= new TreeNode(9);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.right = t6;
        List<Integer> integers = solution.largestValues(t1);
        System.out.println(integers.toString());
    }
    private List<Integer> list = new ArrayList<Integer>();
    public List<Integer> largestValues(TreeNode root) {
        if(root == null)return list;
        Deque<TreeNode> deque = new LinkedList<TreeNode>();
        deque.add(root);
        while(!deque.isEmpty()){
            int max = Integer.MIN_VALUE;
            int size = deque.size();
            for(int i=0;i<size;i++){
                TreeNode poll = deque.poll();
                max = Math.max(poll.val,max);
                if(null != poll.left){
                    deque.add(poll.left);
                }
                if(null != poll.right){
                    deque.add(poll.right);
                }
            }
            list.add(max);
        }
        return list;
    }
}
